//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 算法的时间复杂度应该为 O(log (m+n)) 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -10⁶ <= nums1[i], nums2[i] <= 10⁶ 
// 
//
// Related Topics 数组 二分查找 分治 👍 6525 👎 0

public class Q3_寻找两个正序数组的中位数 {

    //leetcode submit region begin(Prohibit modification and deletion)
    static class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int i = 0;
            int j = 0;
            int N = nums1.length + nums2.length;
            int k = N / 2;
            int pre = Integer.MAX_VALUE;
            int curr = Integer.MAX_VALUE;
            for (int p = 0; p <= k; p++) {
                pre = curr;
                int n1 = i < nums1.length ? nums1[i] : Integer.MAX_VALUE;
                int n2 = j < nums2.length ? nums2[i] : Integer.MAX_VALUE;
                if (n1 < n2) {
                    curr = n1;
                    i++;
                } else {
                    curr = n2;
                    j++;
                }
            }

            if (N % 2 == 0) {
                return (pre + curr) / 2.0;
            } else {
                return curr;
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    static class Test {
        public static void main(String[] args) {
            // Object res = new Solution().findMedianSortedArrays();
            // Sout.println(res);
        }
    }
}
